/*
 * @Author: lei
 * @Description: 二分查找
 * @FilePath: /重学C++/binary_find.cc
 */
// compile: g++ -o binary_find binary_find.cc -std=c++11
// run: ./binary_find
#include <iostream>
#include <vector>
using namespace std;
int BinaryFindAny1(vector<int>& v, int target) {
  // 搜索区间[l,r]
  int l = 0, r = v.size() - 1;
  int mid;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (v[mid] == target)
      return mid;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
  }
  return -1;
}
int BinaryFindAny2(vector<int>& v, int target) {
  // 搜索区间[l,r)
  int l = 0, r = v.size();
  int mid;
  while (l < r) {
    int mid = l + (r - l) / 2;
    if (v[mid] == target)
      return mid;
    else if (v[mid] > target)
      r = mid;
    else if (v[mid] < target)
      l = mid + 1;
  }
  return -1;
}
int BinaryFindLeft1(vector<int>& v, int target) {
  // 搜索区间[l,r]
  int l = 0, r = v.size() - 1;
  int mid;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (v[mid] >= target) r = mid - 1;
    // 如果该值存在于数组中，那么在找到相等值后right边界会不断向左收缩，直到right索引位于target目标值的左边一个索引
    // 下面几种写法同理
    else if (v[mid] < target)
      l = mid + 1;
  }
  // 退出时 l==(r+1)
  if (l >= v.size() || v[l] != target) return -1;
  // 每次使用下标时考虑下标是否合法,下面几种写法同理
  return l;
}
int BinaryFindLeft2(vector<int>& v, int target) {
  // 搜索区间[l,r)
  int l = 0, r = v.size();
  int mid;
  while (l < r) {
    int mid = l + (r - l) / 2;
    if (v[mid] >= target)
      r = mid;
    else if (v[mid] < target)
      l = mid + 1;
  }
  // 退出时 l==r
  if (l >= v.size() || v[l] != target) return -1;
  // if (l >= nums.size() || nums[l] != target) return -1;
  return l;
}
int BinaryFindRight1(vector<int>& v, int target) {
  // 搜索区间[l,r]
  int l = 0, r = v.size() - 1;
  int mid;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (v[mid] <= target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
  }
  // 退出时 l==(r+1)
  if (r < 0 || v[r] != target) return -1;
  return r;
}
int BinaryFindRight2(vector<int>& v, int target) {
  // 搜索区间[l,r)
  int l = 0, r = v.size();
  int mid;
  while (l < r) {
    int mid = l + (r - l) / 2;
    if (v[mid] <= target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
  }
  // 退出时 l==r
  if (r - 1 < 0 || v[r - 1] != target) return -1;
  return r - 1;
}
void Test(vector<int>& v, int target) {
  cout << "-------------Test:-------------" << endl;
  cout << "v:";
  for (const auto& t : v) cout << t << " ";
  cout << endl;
  cout << "target:" << target << endl;
  cout << BinaryFindAny1(v, target) << endl;
  cout << BinaryFindAny2(v, target) << endl;
  cout << BinaryFindLeft1(v, target) << endl;
  cout << BinaryFindLeft2(v, target) << endl;
  cout << BinaryFindRight1(v, target) << endl;
  cout << BinaryFindRight2(v, target) << endl;
}
int main() {
  vector<int> v1{2, 2, 3, 3, 3, 3, 4, 6};
  vector<int> v2{};
  vector<int> v3{2, 4, 4, 7, 8, 10};
  Test(v1, 3);
  Test(v2, 3);
  Test(v3, 6);
  return 0;
}
// 部分参考：https://blog.csdn.net/weixin_43373833/article/details/113763879?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=1
